package leetcode_800;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *OpenTheLock_752 一个四位数的锁 每次只能改变一个数字 问最小次数到达target
 *describe:用广度优先遍历 AC 43%
 *2018年10月17日 上午11:01:38
 */
public class OpenTheLock_752_ {
	
	public static void main(String[] args) {
		OpenTheLock_752_ test=new OpenTheLock_752_();
		/*System.out.println(test.openLock(new String[] 
				{"0201","0101","0102","1212","2002"}, "0202"));*/
		System.out.println(test.openLock(new String[] 
				{"8887","8889","8878","8898","8788","8988","7888","9888"}, "8888"));
	}
	
	 /**
	 * describe:把遍历过的 和锁住的分开  AC 43%
	 * 2018年10月17日 上午11:01:19
	 */
	public int openLock(String[] deadends, String target) {
	       Set<String> seen = new HashSet<>();
	        Set<String> dead = new HashSet<>();
	        for(String deadend : deadends){
	            dead.add(deadend);
	        }
	        
	        if(dead.contains("0000")){
	            return -1;
	        }
	        
	        Queue<String> queue = new LinkedList<>();
	        queue.add("0000");
	        seen.add("0000");
	        int distance = 0;
	        
	        while(queue.size() != 0){
	           
	            int size = queue.size();
	            for(int i = 0; i < size; i++){
	                String now = queue.poll();
	                if(now.equals(target)){
	                    return distance;
	                }
	                for(int j = 0; j < now.length(); j++){
	                    int ch = now.charAt(j)-'0';
	                    int add = (ch+1) % 10;
	                    String temp = now.substring(0, j) + add + now.substring(j+1);
	                    if(!seen.contains(temp) && !dead.contains(temp)){
	                        queue.add(temp);
	                        seen.add(temp);
	                    }
	                    
	                    int minus = (ch+9) % 10;
	                    String temp2 = now.substring(0, j) + minus + now.substring(j+1);
	                    if(!seen.contains(temp2) && !dead.contains(temp2)){
	                        queue.add(temp2);
	                        seen.add(temp2);
	                    }
	                    
	                }
	                
	            }
	            distance++;
	        }
	        
	        return -1;
	    }
	
	
	/**
	 * describe:广度优先遍历 妈的还是超时了 
	 * 2018年10月17日 上午10:45:07
	 */
	public int openLock1(String[] deadends, String target) {
        Queue<String> queue=new LinkedList<String>();
        Set<String> set=new HashSet<String>();
        for(String deadend:deadends) {//从开始就锁住
        	if("0000".equals(deadend))
        		return -1;
        	set.add(deadend);
        }
        queue.offer(target);
        int count=0;
        while(!queue.isEmpty()) {
        	++count;
        	int size=queue.size();
        	while(size!=0) {
        		String now=queue.poll();
        		--size;
        		String[] res=bfs(now);
        		for(int i=0;i<8;++i) {
        			if("0000".equals(res[i]))
        				return count;
        			if(!set.contains(res[i]))
        				queue.offer(res[i]);
        		}
        		set.add(now);//避免死循环
        	}
        }
        return -1;//如果不能再继续遍历 且队列没有元素 即全部锁住
    }
	
	public String[] bfs(String now) {
		char chars[]=now.toCharArray();
		String[] res=new String[8];
		int count=0;
		for(int i=0;i<4;++i) {
			char temp=chars[i];
			chars[i]=(char) (temp=='9'?'0':temp+1);
			res[count++]=new String(chars);
			chars[i]=(char) (temp=='0'?'9':temp-1);
			res[count++]=new String(chars);
			chars[i]=temp;
		}
		return res;
	}
	
}
